首先来看一道例题：
1 | 给定一棵树，支持单点修改单点查询。 |
正常人一看，这不是傻子题，线性都可以。
确实是这样的，那么我们给他加点条件。
1 | 给定一棵树，支持链修改单点查询。 |
现在又如何？
什么？你说上树剖？
那我再来点条件：
$1 \le n,q \le 10^6$。
树剖即使常数再小也是两只 $\log$。
我再来点卡常瞬间凉透。
这时候我们就要学习一种新的比树剖更快的方法解决这类问题。
你可以画一个图，反正我是懒得画了，(逃
这是一棵树，假定我们要修改 5~8 的一条链。
我们发现这可以拆成 $4$ 条路径，分别是 $9 \sim 5 +x$，$9 \sim 8 +x$，那么 $1 \sim 9$ 加了两次，其中 $1$ 是要加一次的，那么我们将 $1 \sim 9 -x$，然后将 $1$ 的父亲到 $9$ 减去 $x$，我们发现这样子就比较好处理了。
首先可以考虑将点查询改成子树查询，那么这边就是变为了查询 $x$ 为根的子树的和，因为一条链如果要对 $x$ 产生贡献，必然是经过它，也就是在它儿子里面。
具体的实现是这样的 $f[u]+x$，$f[v]+x$，$f[lca]-x$，$f[fa[lca]]-x$。
然后查询区间，单点修改区间查询可以使用树状数组来维护，线段树的话常数实在是太大了。
通过这道题目我们发觉，有些查询的东西，可以变化的！
再来看一道题目：
1 | 给定一棵树，支持单点修改链查询。 |
这个和之前那个都是一样的，改成区间修改，单点查询就可以了，更具体的，单点修改就影响了它子树里面的节点，然后你在把查询拆成 $4$ 条路径加一加减一减就可以了。
接下来我们来搞点好玩的题目！
loj 的 DFS 序题目，目前我已经全部做完了。
这个树状数组，查询区间和就可以了。
这很简单！
这个如果使用线段树也可以过掉，但我在这里介绍一种更巧妙，常数更小，代码量也更小的树状数组写法。
首先考虑用差分维护区间加，那么区间和即为：
$\sum \limits _{i=l}^r \sum \limits _{j=1}^i f[j]$。
这个东西实在是太难搞了，我们考虑计算 $1 \sim r$ 的总和。
总和为 $\sum \limits _{j=1}^r f[j] \times (r-j+1)$。
然后两个前缀和一样的东西减一减就可以了，$\sum \limits _{j=1}^r f[j] \times (r-j+1) - \sum \limits _{j=1}^l f[j] \times (l-j+1)$。
这个东西出来了，我们再进一步简化刚才那个 $1 \sim r$ 的柿子。
总和为 $r \times \sum \limits _{j=1}^r f[j]- \sum \limits _{j=1}^r f[j] \times(j-1)$。
这个东西应该比较好维护，就维护两个树状数组一个是差分数组的区间和，一个是乘 $j-1$ 的。
这东西乍一看不太好搞，我们还是一步一步来。
假设没有第三个操作，我们可以考虑将链拆开变为四条链，用子树和来维护。
但是又有查询子树和，这该怎么搞呢？
我们考虑一下，假定一条链在一个节点内的子树，那么必然，它会对子树产生贡献。
那贡献是多大呢？
假定 $u,v$ 分别是查询的节点的子树，与链修改的一个节点在 $u$ 的子树内。
就是 $a_v \times (dep_{v}-dep_{u}+1)$，我们发现这个东西不太好维护。
我们尝试将它拆开来得到 $a_v \times dep_{v}-a_v \times (dep_{u}+1)$。
前面那个东西可以用另一颗树状数组来维护，后面那个东西可以把 $a_v$ 提出然后统计和。
总时间复杂度 $O(n \log n)$，但是由于 loj 的出题人丧心病狂卡常，只能用树状数组来维护，并且要上树剖求 LCA，如果你常数比较大。
我使用了 fread + fwrite 才将它在不开 O2 前提下卡进了 2S。
这次换了一个形式，是要求子树加，链查询。
这东西也很好搞，我们先单纯的考虑单点修改。
将链拆成四条之后，我们发觉单点修改会对他子树里面的点都产生贡献。
也就是会对于 $[a,a+sz[a]-1]$ 的这些点产生贡献。
考虑直接使用差分去做。
当前它的贡献也很好算。
那么我们再考虑一下子树和，我们会发现当前子树和产生的贡献是：
假定 $u,v$ 分别为需要修改的子树的根，查询到根节点的链和。
那么当前所产生的贡献是 $(dep_{v}-dep_{u}+1)*a_u$，
欸这东西是不是和我们之前的那个东西神似 (
拆开！得到 $dep_{v} \times a_u+(1-dep_{u}) \times a_u$ 前面那个东西可以用另一个树状数组求和，后面那个东西扔到之前那个差分树状数组就可以了。
至此 DFS 序的东西已经到这里差不多结束了！
如有问题还请指出！！！